class Solution {
    int[] tmpNums;
    public int reversePairs(int[] nums) {
        int len = nums.length;
        tmpNums = new int[len];
        return mergeSort(nums, 0, len - 1);
    }
    private int mergeSort(int[] nums, int left, int right){
        if(left >= right) return 0;
        int mid = (left + right) / 2;
        int ret = 0;
        ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid + 1, right);
        //1. 合并两个有序数组之前，需要统计翻转对的个数
        int cur1 = left;
        int cur2 = mid + 1;
        while(cur1 <= mid && cur2 <= right){
            // if(nums[cur1] / 2.0 > nums[cur2]){
            //     ret += (right - cur2 + 1);
            //     cur1++;
            // }else{
            //     cur2++;
            // }

            if(nums[cur1] / 2.0 > nums[cur2]){
                ret += mid - cur1 + 1;
                cur2++;
            }else{
                cur1++;
            }
        }
        //2. 合并两个有序数组 - 降序
        cur1 = left;
        cur2 = mid + 1;
        int i = 0;
        while(cur1 <= mid && cur2 <= right){
            if(nums[cur1] > nums[cur2]){
                tmpNums[i++] = nums[cur2++];
            }else{
                tmpNums[i++] = nums[cur1++];
            }
        }
        while(cur1 <= mid){
            tmpNums[i++] = nums[cur1++];
        }
        while(cur2 <= right){
            tmpNums[i++] = nums[cur2++];
        }
        for(int j = left; j <= right; j++){
            nums[j] = tmpNums[j - left];
        }

        return ret;
    }
}